% visualize_gantt_chart.m
% 绘制内存布局的甘特图，展示每个buffer在时间和空间上的分布。

function fig = visualize_gantt_chart(history, type_code_to_plot, capacity)
    
    fig = figure('Name', sprintf('内存布局甘特图 (Cache Type %d)', type_code_to_plot));
    % 提高渲染流畅度
    set(gcf, 'Renderer', 'opengl');
    
    % 若未记录块明细（减少内存/时间），则直接退出
    if isempty(history.allocated_blocks)
        title(sprintf('内存布局甘特图 (Cache Type %d) - 明细未记录，已跳过绘制', type_code_to_plot));
        xlabel('调度步骤 (Step)'); ylabel('内存地址'); grid on; ylim([0, capacity]); xlim([0, length(history.steps)]);
        return;
    end
    
    % 获取所有出现过的 buf_id，并统计出现步数（用于Top-K筛选）
    all_buf_ids = [];
    present_count = containers.Map('KeyType','int32','ValueType','double');
    S = size(history.allocated_blocks, 1);
    for i = 1:S
        blocks = history.allocated_blocks{i, type_code_to_plot};
        if ~isempty(blocks)
            ids_i = int32([blocks.buf_id]);
            all_buf_ids = [all_buf_ids, ids_i]; %#ok<AGROW>
            % 计数：每步出现则+1
            for k = 1:numel(ids_i)
                bid = ids_i(k);
                if isKey(present_count, bid)
                    present_count(bid) = present_count(bid) + 1;
                else
                    present_count(bid) = 1;
                end
            end
        end
    end
    unique_buf_ids = unique(all_buf_ids);

    % =====================================================================
    % [Perf-Option] 限制绘制对象规模：仅绘制Top-K出现频次最高的buffer
    % =====================================================================
    enable_gantt_top_k = true;          % 需要时可关闭
    gantt_top_k_buffers = 300;          % 大图建议 200-500
    if enable_gantt_top_k && ~isempty(unique_buf_ids)
        % 将 (buf_id, count) 转为矩阵排序
        buf_ids_vec = int32(unique_buf_ids(:));
        counts_vec = zeros(size(buf_ids_vec));
        for idx = 1:numel(buf_ids_vec)
            bid = buf_ids_vec(idx);
            if isKey(present_count, bid)
                counts_vec(idx) = present_count(bid);
            else
                counts_vec(idx) = 0;
            end
        end
        [~, order] = sort(counts_vec, 'descend');
        if numel(order) > gantt_top_k_buffers
            order = order(1:gantt_top_k_buffers);
        end
        unique_buf_ids = buf_ids_vec(order).';
    end
    
    color_map = containers.Map('KeyType','int32','ValueType','any');
    if ~isempty(unique_buf_ids)
        colors = jet(length(unique_buf_ids)); % 使用jet色谱
        for i=1:length(unique_buf_ids)
            color_map(unique_buf_ids(i)) = colors(i,:);
        end
    end

    hold on;
    
    % =====================================================================
    % [Perf-Option 2/2] 合段绘制：连续相同步骤中同一块的 (start,size) 不变时合并为一段
    % 显著减少 rectangle 数量：O(段数) 替代 O(步骤×块数)
    % =====================================================================
    S = length(history.steps);
    % 跳过重复绘制：记录每个buffer下一次允许绘制的步号
    skip_until = containers.Map('KeyType','int32','ValueType','double');
    for i = 1:S
        blocks = history.allocated_blocks{i, type_code_to_plot};
        if isempty(blocks), continue; end
        
        % 以 (buf_id,start,size) 为 key 做 run-length 合段
        for b = 1:length(blocks)
            block = blocks(b);
            bid = int32(block.buf_id);
            % 若该buffer在此前已画过一段且覆盖到当前步，则跳过
            if isKey(skip_until, bid) && skip_until(bid) > i
                continue;
            end
            run_len = 1;
            % 向后延伸，直到变化
            j = i + 1;
            while j <= S
                blocks_next = history.allocated_blocks{j, type_code_to_plot};
                if isempty(blocks_next)
                    break;
                end
                % 在下一步中查找同一 buf_id 的块是否存在且起始与大小相同
                idx = find([blocks_next.buf_id] == block.buf_id, 1);
                if isempty(idx)
                    break;
                end
                nxt = blocks_next(idx);
                if nxt.start ~= block.start || nxt.size ~= block.size
                    break;
                end
                run_len = run_len + 1;
                j = j + 1;
            end
            
            % 绘制合并后的矩形，宽度 = run_len
            pos = [i - 0.5, block.start, run_len, block.size];
            if isKey(color_map, block.buf_id)
                rectangle('Position', pos, 'FaceColor', color_map(block.buf_id), 'EdgeColor', 'none');
            else
                rectangle('Position', pos, 'FaceColor', [0.5 0.5 0.5], 'EdgeColor', 'none');
            end

            % 标记该buffer在此段结束前无需再绘制
            skip_until(bid) = i + run_len;
        end
        
        % 步级跳过可进一步加速，但为保持实现简单与稳健，此处依赖 skip_until 控制重复绘制
    end
    
    hold off;
    
    % 设置图表格式
    xlim([0, length(history.steps)]);
    ylim([0, capacity]);
    title(sprintf('内存布局甘特图 (Cache Type %d)', type_code_to_plot));
    xlabel('调度步骤 (Step)');
    ylabel('内存地址');
    grid on;

end